#include <iostream>
#include <vector>
using namespace std;

void countSort(vector<int>& res){
	int len = res.size();
	vector<int> cnt(len + 1 , 0);
	int max = res[0];
	for(int i = 0; i < len ; i++){
		if(res[i] > max){
			max = res[i];
		}
	}
	for(int i = 0;i <= max;i++){
		cnt[res[i]]++;
	}
	int j = 0;
	int index = 0;
	
	while(cnt[j] >= 0&&j <= max){
		if(cnt[j] == 0){
			j++;
			continue;
		}
		res[index++] = j;
		cnt[j]--;
	}
} 

int main(){
	int arr[] = {1,9,4,5,2,2,4,7,8,7};
	vector<int> res(arr,arr+10);
	countSort(res);
	vector<int>::iterator ite = res.begin();
	for(;ite != res.end();ite++){
		cout<< *ite <<" ";
	}
	system("pause");
	return 0;
}
